#include <iostream>
#include <queue>
using namespace std;

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertexNum 100

typedef struct AdjVode *PtrToAdjVNode;
struct AdjVode {
    int AdjV;//邻接点下标
    PtrToAdjVNode Next;
};
bool V_visit[MaxVertexNum];
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    AdjList G; //邻接表
};
typedef PtrToGNode LGraph;
void DFS_Connect(LGraph G, int vertex_i);
LGraph CreateGraph(int N);
LGraph Insert(LGraph G, int v1, int v2);
void BFS_Connect(LGraph G, int vertex_i);
int main()
{

    int N, E;
    int v1, v2;
    LGraph G;
    scanf("%d %d", &N, &E);
    G = CreateGraph(N);
    for (int i = 0; i < E;i++)
    {
        scanf("%d %d", &v1, &v2);
        G = Insert(G, v1, v2);
    }
    //DFS print
    for (int i = 0; i < G->Nv;i++)
    {
        if(!V_visit[i])
        {
            printf("{ ");
            printf("%d ", i);
            DFS_Connect(G, i);
            printf("}\n");
        }
            
    }
    
    //BFS print
    for (int i = 0; i < G->Nv;i++)
    {
        V_visit[i] = false;
    }
    
    for (int i = 0; i < G->Nv;i++)
    {
        if(!V_visit[i])
        {
            printf("{ ");
            printf("%d ", i);
            BFS_Connect(G, i);
            printf("}\n");
        }

    }
    
    return 0;

}
void DFS_Connect(LGraph G,int vertex_i)
{
    V_visit[vertex_i] = true;
    PtrToAdjVNode W;
    for (W = G->G[vertex_i].FirstEdge; W; W = W->Next)
        if(!V_visit[W->AdjV])
        {
            printf("%d ", W->AdjV);
            DFS_Connect(G, W->AdjV);
        }
}
queue<PtrToAdjVNode> myqueue;
void BFS_Connect(LGraph G,int vertex_i)
{
    V_visit[vertex_i] = true;
    PtrToAdjVNode W;
    for (W = G->G[vertex_i].FirstEdge; W; W = W->Next)
        myqueue.push(W);
    while(!myqueue.empty())
    {
        W = myqueue.front();
        if(W==NULL)
        {
            myqueue.pop();
            continue;
        }
        vertex_i = W->AdjV;
        myqueue.pop();
        if(!V_visit[vertex_i])
        {
            printf("%d ", vertex_i);
            V_visit[vertex_i] = true;
            while(W)
            {
                
                if(W!=NULL)
                {
                    vertex_i = W->AdjV;
                    for (W = G->G[vertex_i].FirstEdge; W; W = W->Next)
                        myqueue.push(W);
                }

            }
        }
    }

}
LGraph CreateGraph(int N)
{
    LGraph G;
    G = (LGraph)malloc(sizeof(struct GNode));
    G->Nv = N;
    G->Ne = 0;
    for (int i = 0; i < G->Nv;i++)
        G->G[i].FirstEdge = NULL;
    return G;
}
LGraph Insert(LGraph G, int v1, int v2)
{
    PtrToAdjVNode NewNode;
    PtrToAdjVNode W,W_next;
    int temp;
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVode));
    NewNode->AdjV = v2;
    V_visit[v1] = false;
    
    NewNode->Next = G->G[v1].FirstEdge;
    G->G[v1].FirstEdge = NewNode;

    for (W = G->G[v1].FirstEdge; W; W = W->Next)
    {
        W_next = W->Next;
        if(W_next==NULL)
            break;
        else
        {
            if(W->AdjV > W_next->AdjV)
            {
                temp = W_next->AdjV;
                W_next->AdjV = W->AdjV;
                W->AdjV = temp;
            }
        }
    }


    //无向图还需在v2,v1
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVode));
    NewNode->AdjV = v1;
    V_visit[v2] = false;

    NewNode->Next = G->G[v2].FirstEdge;
    G->G[v2].FirstEdge = NewNode;

    for (W = G->G[v2].FirstEdge; W; W = W->Next)
    {
        W_next = W->Next;
        if(W_next==NULL)
            break;
        else
        {
            if(W->AdjV > W_next->AdjV)
            {
                temp = W_next->AdjV;
                W_next->AdjV = W->AdjV;
                W->AdjV = temp;
            }
        }
    }


    return G;
}